
//1. 两数之和:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++)
        {
            auto it = hash.find(target-nums[i]);
            if(it != hash.end())
            {
                return {i, it->second};
            }
            hash[nums[i]] = i;
        }

        return {};
    }
};


//2. 字母异位词分组
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        unordered_map<string, vector<string>> hash;
        for(auto& ch : strs)
        {
            auto tmp = ch;
            sort(tmp.begin(), tmp.end());
            hash[tmp].emplace_back(ch);
        }

        vector<vector<string>> ret;
        for(auto it = hash.begin(); it != hash.end(); it++)
        {
            ret.emplace_back(it->second);
        }
        return ret;
    }
};


//3. 最长连续子序列
class Solution {
public:
    int longestConsecutive(vector<int>& nums) 
    {
        unordered_set<int> hash;
        for(auto& i : nums)
        {
            hash.insert(i);
        }

        int len = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(!hash.count(nums[i] - 1))
            {
                int curlen = 1;
                int curnum = nums[i];
                while(hash.count(curnum+1))
                {
                    curnum += 1;
                    curlen += 1;
                } 
                len = max(len, curlen);
            }
        }
        return len;
    }
};


//4. 移动零;
class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        int left = 0, right = 0;
        while(right < nums.size())
        {
            if(nums[right] == 0) right++;
            else swap(nums[left++], nums[right++]);
        }
    }
};


//5. 盛水最多的容器;
class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int n = height.size();
        int left = 0, right = n - 1;
        int ret = 0;
        while(left < right)
        {
            int tmp = min(height[left], height[right]);
            ret = max(ret, tmp * (right - left));
            if(height[left] < height[right]) left++;
            else right--;
        }
        return ret;
    }
};


//6. 三数之和;
class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        for(int i = 0; i < n; )
        {
            int left = i + 1, right = n - 1;
            int target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left-1]) left++;
                    while(left < right && nums[right] == nums[right+1]) right--;
                }
            }
            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
};


//7. 接雨水
class Solution 
{
public:
    int trap(vector<int>& height) 
    {
        int n = height.size();
        vector<int> leftmax(n), rightmax(n);
        leftmax[0] = height[0], rightmax[n-1] = height[n-1];

        for(int i = 1; i < n; i++)
            leftmax[i] = max(leftmax[i-1], height[i]);

        for(int i = n - 2; i >= 0; i--)
            rightmax[i] = max(rightmax[i+1], height[i]);

        int ret = 0;
        for(int i = 1; i < n - 1; i++)
            ret += min(leftmax[i], rightmax[i]) - height[i];
        
        return ret;
    }
};


//8. 无重复字符的最长子串:
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> hash;
        int ret = 0;
        int left = 0, right = 0;
        while(right < s.size())
        {
            hash[s[right]]++;
            while(hash[s[right]] > 1)
            {
                hash[s[left++]]--;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};


//9. 找到字符串中所有的异位词
class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        int ssize = s.size(), psize = p.size();
        vector<int> scount(26); vector<int> pcount(26);
        if(ssize < psize) return {};

        for(int i = 0; i < psize; i++)
        {
            scount[s[i] - 'a']++;
            pcount[p[i] - 'a']++;
        }

        vector<int> ret;
        if(scount == pcount)
            ret.push_back(0);

        for(int i = 0; i < ssize - psize; i++)
        {
            scount[s[i] - 'a']--;
            scount[s[i+psize] - 'a']++;
            if(scount == pcount)
                ret.emplace_back(i + 1);
        }
        return ret;
    }
};